Decision Algorithms for Fibonacci-Automatic Words, with Applications to Pattern Avoidance

摘要

We implement a decision procedure for answering questions about a class ofinfinite words that might be called (for lack of a better name)"Fibonacci-automatic". This class includes, for example, the famous Fibonacciword f = 01001010..., the fixed point of the morphism 0 -> 01 and 1 -> 0. Wethen recover many results about the Fibonacci word from the literature (andimprove some of them), such as assertions about the occurrences in f ofsquares, cubes, palindromes, and so forth. As an application of our method weprove a new result: there exists an aperiodic infinite binary word avoiding thepattern x x x^R. This is the first avoidability result concerning a nonuniformmorphism proven purely mechanically.